{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Merge BSTs to Create Single BST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #hash-table #binary-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #哈希表 #二分查找 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canMerge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合并多棵二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你 <code>n</code> 个 <strong>二叉搜索树的根节点</strong> ，存储在数组 <code>trees</code> 中（<strong>下标从 0 开始</strong>），对应 <code>n</code> 棵不同的二叉搜索树。<code>trees</code> 中的每棵二叉搜索树 <strong>最多有 3 个节点</strong> ，且不存在值相同的两个根节点。在一步操作中，将会完成下述步骤：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择两个 <strong>不同的</strong> 下标 <code>i</code> 和 <code>j</code> ，要求满足在&nbsp;<code>trees[i]</code> 中的某个 <strong>叶节点</strong> 的值等于&nbsp;<code>trees[j]</code> 的 <strong>根节点的值</strong> 。</li>\n",
    "\t<li>用&nbsp;<code>trees[j]</code> 替换 <code>trees[i]</code> 中的那个叶节点。</li>\n",
    "\t<li>从 <code>trees</code> 中移除 <code>trees[j]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果在执行 <code>n - 1</code> 次操作后，能形成一棵有效的二叉搜索树，则返回结果二叉树的 <strong>根节点</strong> ；如果无法构造一棵有效的二叉搜索树<em>，</em>返回<em> </em><code>null</code> 。</p>\n",
    "\n",
    "<p>二叉搜索树是一种二叉树，且树中每个节点均满足下述属性：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>任意节点的左子树中的值都 <strong>严格小于</strong>&nbsp;此节点的值。</li>\n",
    "\t<li>任意节点的右子树中的值都 <strong>严格大于</strong>&nbsp;此节点的值。</li>\n",
    "</ul>\n",
    "\n",
    "<p>叶节点是不含子节点的节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/08/d1.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>trees = [[2,1],[3,2,5],[5,4]]\n",
    "<strong>输出：</strong>[3,2,5,1,null,4]\n",
    "<strong>解释：</strong>\n",
    "第一步操作中，选出 i=1 和 j=0 ，并将 trees[0] 合并到 trees[1] 中。\n",
    "删除 trees[0] ，trees = [[3,2,5,1],[5,4]] 。\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/24/diagram.png\" />\n",
    "在第二步操作中，选出 i=0 和 j=1 ，将 trees[1] 合并到 trees[0] 中。\n",
    "删除 trees[1] ，trees = [[3,2,5,1,null,4]] 。\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/24/diagram-2.png\" />\n",
    "结果树如上图所示，为一棵有效的二叉搜索树，所以返回该树的根节点。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/08/d2.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>trees = [[5,3,8],[3,2,6]]\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>\n",
    "选出 i=0 和 j=1 ，然后将 trees[1] 合并到 trees[0] 中。\n",
    "删除 trees[1] ，trees = [[5,3,8,2,6]] 。\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/24/diagram-3.png\" />\n",
    "结果树如上图所示。仅能执行一次有效的操作，但结果树不是一棵有效的二叉搜索树，所以返回 null 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/08/d3.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>trees = [[5,4],[3]]\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>无法执行任何操作。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == trees.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li>每棵树中节点数目在范围 <code>[1, 3]</code> 内。</li>\n",
    "\t<li>输入数据的每个节点可能有子节点但不存在子节点的子节点</li>\n",
    "\t<li><code>trees</code> 中不存在两棵树根节点值相同的情况。</li>\n",
    "\t<li>输入中的所有树都是 <strong>有效的二叉树搜索树</strong> 。</li>\n",
    "\t<li><code>1 &lt;= TreeNode.val &lt;= 5 * 10<sup>4</sup></code>.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [merge-bsts-to-create-single-bst](https://leetcode.cn/problems/merge-bsts-to-create-single-bst/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [merge-bsts-to-create-single-bst](https://leetcode.cn/problems/merge-bsts-to-create-single-bst/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,1],[3,2,5],[5,4]]', '[[5,3,8],[3,2,6]]', '[[5,4],[3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "\n",
    "        mx = 50001\n",
    "        is_sub = [False] * mx\n",
    "        roots = [None] * mx\n",
    "\n",
    "        for rt in trees:\n",
    "            if rt.left:\n",
    "                if is_sub[rt.left.val]:\n",
    "                    return None\n",
    "                is_sub[rt.left.val] = True\n",
    "\n",
    "            if rt.right:\n",
    "                if is_sub[rt.right.val]:\n",
    "                    return None\n",
    "                is_sub[rt.right.val] = True\n",
    "\n",
    "            roots[rt.val] = rt\n",
    "\n",
    "        root = None\n",
    "        for rt in trees:\n",
    "            if not is_sub[rt.val]:\n",
    "                if root is not None:\n",
    "                    return None\n",
    "                root = rt\n",
    "\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        cnt = [0]\n",
    "\n",
    "        def build(node, l, r):\n",
    "            cnt[0] += 1\n",
    "            if node.left:\n",
    "                if node.left.val <= l:\n",
    "                    return None\n",
    "                if lo := roots[node.left.val]:\n",
    "                    node.left = build(lo, l, node.val)\n",
    "                    if node.left is None:\n",
    "                        return None\n",
    "\n",
    "            if node.right:\n",
    "                if node.right.val >= r:\n",
    "                    return None\n",
    "                if ro := roots[node.right.val]:\n",
    "                    node.right = build(ro, node.val, r)\n",
    "                    if node.right is None:\n",
    "                        return None\n",
    "\n",
    "            return node\n",
    "\n",
    "        root = build(root, 0, mx)\n",
    "        if cnt[0] == len(trees):\n",
    "            return root\n",
    "\n",
    "        return None\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "def checkBST(root: TreeNode) -> tuple[bool, int, int]:\r\n",
    "    if root.left is None and root.right is None:\r\n",
    "        return True, root.val, root.val\r\n",
    "    if root.left is None:\r\n",
    "        rightBST, rightMin, rightMax = checkBST(root.right)\r\n",
    "        return rightBST and root.val < rightMin, root.val, rightMax\r\n",
    "    if root.right is None:\r\n",
    "        leftBST, leftMin, leftMax = checkBST(root.left)\r\n",
    "        return leftBST and root.val > leftMax, leftMin, root.val\r\n",
    "\r\n",
    "    leftBST, leftMin, leftMax = checkBST(root.left)\r\n",
    "    rightBST, rightMin, rightMax = checkBST(root.right)\r\n",
    "    return leftBST and rightBST and leftMax < root.val < rightMin, leftMin, rightMax\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\r\n",
    "        # find leaves\r\n",
    "        m = 50001\r\n",
    "        n = 0\r\n",
    "        leaves: dict[int, tuple[int, int]] = dict()\r\n",
    "        for i, node in enumerate(trees):\r\n",
    "            _, l, r = checkBST(node)\r\n",
    "            m = min(m, l)\r\n",
    "            n = max(n, r)\r\n",
    "            # node with no children is not considered as leaf\r\n",
    "            # because no roots having same val, therefore no other tree can merge to it\r\n",
    "            if node.left is not None:\r\n",
    "                if node.left.val in leaves:\r\n",
    "                    return None\r\n",
    "                leaves[node.left.val] = (i, 0)\r\n",
    "            if node.right is not None:\r\n",
    "                if node.right.val in leaves:\r\n",
    "                    return None\r\n",
    "                leaves[node.right.val] = (i, 1)\r\n",
    "        \r\n",
    "        # find root\r\n",
    "        root = None\r\n",
    "        for node in trees:\r\n",
    "            # all roots needs to match with one leaf, except one as final root\r\n",
    "            if node.val not in leaves:\r\n",
    "                if root is not None:\r\n",
    "                    return None\r\n",
    "                root = node\r\n",
    "        \r\n",
    "        if root is None:\r\n",
    "            root = trees[0]\r\n",
    "\r\n",
    "        # build tree\r\n",
    "        for node in trees:\r\n",
    "            if node is not root:\r\n",
    "                if leaves[node.val][1] == 0:\r\n",
    "                    trees[leaves[node.val][0]].left = node\r\n",
    "                else:\r\n",
    "                    trees[leaves[node.val][0]].right = node\r\n",
    "\r\n",
    "        b, l, r = checkBST(root)\r\n",
    "        return root if b and l == m and r == n else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def search(self, n):\n",
    "        if n:\n",
    "            if n.val in self.dp:\n",
    "                n = self.dp[n.val]\n",
    "                del self.dp[n.val]\n",
    "                n.left = self.search(n.left)\n",
    "                n.right = self.search(n.right)\n",
    "            return n\n",
    "\n",
    "    def check(self, n):\n",
    "        if n:\n",
    "            l = self.check(n.left)\n",
    "            if not l[0]:\n",
    "                return False, None, None\n",
    "            r = self.check(n.right)\n",
    "            if not r[0]:\n",
    "                return False, None, None\n",
    "            return l[2]<n.val<r[1], min(n.val, l[1]), max(n.val, r[2])\n",
    "        return True, 10**5, 0\n",
    "\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.dp = dp = {i.val: i for i in trees}\n",
    "        s = {}\n",
    "        for i in trees:\n",
    "            if not i.val in s:\n",
    "                s[i.val] = i.val\n",
    "            if i.left:\n",
    "                s[i.left.val] = i.val\n",
    "            if i.right:\n",
    "                s[i.right.val] = i.val\n",
    "\n",
    "        i = list(s.keys())[0]\n",
    "        d = {list(s.keys())[0]}\n",
    "        while not i == s[i]:\n",
    "            i = s[i]\n",
    "            if i in d:\n",
    "                return None\n",
    "            d.add(i)\n",
    "\n",
    "        p = dp[i]\n",
    "        self.search(p)\n",
    "\n",
    "        if dp:\n",
    "            return None\n",
    "        if not self.check(p)[0]:\n",
    "            return None\n",
    "\n",
    "        return p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        leaf = {}\n",
    "        n = len(trees)\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree.left:\n",
    "                leaf[tree.left.val] = [tree, 0, False]\n",
    "            if tree.right:\n",
    "                leaf[tree.right.val] = [tree, 1, False]\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "\n",
    "            if trees[i].val in leaf:\n",
    "\n",
    "                pa = leaf[trees[i].val][0]\n",
    "                if leaf[trees[i].val][1]:\n",
    "                    pa.right = trees[i]\n",
    "                else:\n",
    "                    pa.left = trees[i]\n",
    "                del trees[i]\n",
    "                \n",
    "        if len(trees) != 1:\n",
    "            return None\n",
    "        \n",
    "        tag = True\n",
    "        prev = 0\n",
    "        def dfs(root):\n",
    "            nonlocal prev\n",
    "            # print(root.val, (l, r))\n",
    "            # if not root.left and not root.right:\n",
    "            #     return True\n",
    "            if root.left:\n",
    "                leaf[root.left.val][2] = True\n",
    "                if not dfs(root.left):\n",
    "                    return False\n",
    "            print(root.val, prev)\n",
    "            if root.val <= prev:\n",
    "                return False\n",
    "            prev = root.val\n",
    "            if root.right:\n",
    "                leaf[root.right.val][2] = True\n",
    "                if not dfs(root.right):\n",
    "                    return False\n",
    "            return True \n",
    "\n",
    "        tag = dfs(trees[-1])\n",
    "        if tag:\n",
    "            for lf in leaf:\n",
    "                # print(\"lf\", lf)\n",
    "                if leaf[lf][2] == False:\n",
    "                    # print(\"222\", leaf[lf])\n",
    "                    return None\n",
    "            return trees[0]\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.link = 0\n",
    "        dic = {}\n",
    "        leaves = set()\n",
    "        for t in trees:\n",
    "            dic[t.val] = t \n",
    "            if t.left:\n",
    "                leaves.add(t.left.val)\n",
    "            if t.right:\n",
    "                leaves.add(t.right.val)\n",
    "        roots = [node for node in trees if node.val not in leaves]\n",
    "        if len(roots) != 1:\n",
    "            return None\n",
    "        n = len(trees)\n",
    "        def dfs(node):\n",
    "            if self.link > n - 1:\n",
    "                return \n",
    "            if node.left and node.left.val in dic:\n",
    "                self.link += 1 \n",
    "                node.left = dic[node.left.val]\n",
    "                dfs(node.left)\n",
    "            if node.right and node.right.val in dic:\n",
    "                self.link += 1 \n",
    "                node.right = dic[node.right.val]\n",
    "                dfs(node.right)\n",
    "        dfs(roots[0])\n",
    "        if self.link != n - 1:\n",
    "            return None \n",
    "        def check(root, curMax, curMin):\n",
    "            if not root:\n",
    "                return True \n",
    "            if root.val >= curMax or root.val <= curMin:\n",
    "                return False \n",
    "            return check(root.left, root.val, curMin) and check(root.right, curMax, root.val)\n",
    "        return roots[0] if check(roots[0], float('inf'), - float('inf')) else None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.link = 0\n",
    "        dic = {}\n",
    "        leaves = set()\n",
    "        for t in trees:\n",
    "            dic[t.val] = t \n",
    "            if t.left:\n",
    "                leaves.add(t.left.val)\n",
    "            if t.right:\n",
    "                leaves.add(t.right.val)\n",
    "        roots = [node for node in trees if node.val not in leaves]\n",
    "        if len(roots) != 1:\n",
    "            return None\n",
    "        n = len(trees)\n",
    "        def dfs(node):\n",
    "            if self.link > n - 1:\n",
    "                return \n",
    "            if node.left and node.left.val in dic:\n",
    "                self.link += 1 \n",
    "                node.left = dic[node.left.val]\n",
    "                dfs(node.left)\n",
    "            if node.right and node.right.val in dic:\n",
    "                self.link += 1 \n",
    "                node.right = dic[node.right.val]\n",
    "                dfs(node.right)\n",
    "        dfs(roots[0])\n",
    "        if self.link != n - 1:\n",
    "            return None \n",
    "        def check(root, curMax, curMin):\n",
    "            if not root:\n",
    "                return True \n",
    "            if root.val >= curMax or root.val <= curMin:\n",
    "                return False \n",
    "            return check(root.left, root.val, curMin) and check(root.right, curMax, root.val)\n",
    "        return roots[0] if check(roots[0], float('inf'), - float('inf')) else None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        n = len(trees)\n",
    "        leaf = set()\n",
    "        val_root = dict()\n",
    "        for tree in trees:\n",
    "            if tree.left:\n",
    "                leaf.add(tree.left.val)\n",
    "            if tree.right:\n",
    "                leaf.add(tree.right.val)\n",
    "            val_root[tree.val] = tree\n",
    "\n",
    "        root = None\n",
    "        for tree in trees:\n",
    "            if tree.val not in leaf:\n",
    "                if root is not None: return None\n",
    "                root = tree\n",
    "\n",
    "        if root is None: return None\n",
    "        \n",
    "        def dfs(node: Optional[TreeNode], l: int, r: int) -> bool:\n",
    "            nonlocal n\n",
    "            if node.left:\n",
    "                if node.left.val <= l: return False\n",
    "                if node.left.val in val_root:\n",
    "                    node.left = val_root[node.left.val]\n",
    "                    if not dfs(node.left, l, node.val): return False\n",
    "                    n -= 1\n",
    "            if node.right:\n",
    "                if node.right.val >= r: return False\n",
    "                if node.right.val in val_root:\n",
    "                    node.right = val_root[node.right.val]\n",
    "                    if not dfs(node.right, node.val, r): return False\n",
    "                    n -= 1\n",
    "            return True\n",
    "\n",
    "        if not dfs(root, -inf, inf) or n != 1: return None\n",
    "\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        seen = set()\n",
    "        dic = defaultdict(list)\n",
    "        for t in trees:\n",
    "            dic[t.val] = [None, None]\n",
    "            seen.add(t.val)\n",
    "            if t.left:\n",
    "                seen.add(t.left.val)\n",
    "                dic[t.val][0] = t.left.val\n",
    "            if t.right:\n",
    "                seen.add(t.right.val)\n",
    "                dic[t.val][1] = t.right.val\n",
    "\n",
    "        # 父节点数组\n",
    "        fa = list(range(max(seen) + 1))\n",
    "\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            x, y = find(x), find(y)\n",
    "            if x != y:\n",
    "                fa[x] = y\n",
    "\n",
    "        for t in trees:\n",
    "            if t.left:\n",
    "                union(t.left.val, t.val)\n",
    "            if t.right:\n",
    "                union(t.right.val, t.val)\n",
    "\n",
    "        root = TreeNode(find(trees[0].val))\n",
    "        q = deque([(root, inf, -inf)])\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            node, l, r = q.popleft()\n",
    "            cnt += 1\n",
    "            if node.val >= l or node.val <= r:\n",
    "                return None\n",
    "            if dic[node.val]:\n",
    "                if dic[node.val][0]:\n",
    "                    node.left = TreeNode(dic[node.val][0])\n",
    "                    q.append((node.left, min(l, node.val), r))\n",
    "                if dic[node.val][1]:\n",
    "                    node.right = TreeNode(dic[node.val][1])\n",
    "                    q.append((node.right, l, max(node.val, r)))\n",
    "\n",
    "        if cnt != len(seen):\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMerge(self, trees):\n",
    "        root=dict()\n",
    "        index=dict()\n",
    "        for x,target in enumerate(trees):\n",
    "            root[target.val]=target\n",
    "            index[target.val]=x\n",
    "        saf=list()\n",
    "        def findleef(i):\n",
    "            if i.left==None and i.right==None:\n",
    "                return i.val\n",
    "            else:\n",
    "                if i.left!=None:\n",
    "                    son=findleef(i.left)\n",
    "                    if son!=0:\n",
    "                        ans.append((son,i,0))\n",
    "                if i.right!=None:\n",
    "                    son=findleef(i.right)\n",
    "                    if son!=0:\n",
    "                        ans.append((son,i,1))\n",
    "                return 0\n",
    "            \n",
    "        for i in trees:\n",
    "            ans=list()\n",
    "            findleef(i)\n",
    "            saf.append(ans)\n",
    "        R=0\n",
    "        while len(root)>1 and R<len(saf):\n",
    "            x=0\n",
    "            flag=0\n",
    "            if saf[R]==None:\n",
    "                R+=1\n",
    "                continue\n",
    "            while x<len(saf[R]): \n",
    "                i=saf[R][x]\n",
    "                if i[0] in root :\n",
    "                    if i[0]==trees[R].val:\n",
    "                        return None\n",
    "                    flag=1\n",
    "                    f=i[1]\n",
    "                    if i[2]==0:\n",
    "                        f.left=root[i[0]]\n",
    "                    else:\n",
    "                        f.right=root[i[0]]\n",
    "                    del root[i[0]]\n",
    "                    n=index[i[0]]\n",
    "                    del index[i[0]]\n",
    "                    \n",
    "                    if trees[n].left==None and trees[n].right==None:\n",
    "                        continue\n",
    "                    else:\n",
    "                        del saf[R][x]\n",
    "                        x-=1\n",
    "                        saf[R].extend(saf[n])\n",
    "                    saf[n]=None\n",
    "                x+=1\n",
    "            R+=1\n",
    "        if len(index)==1:\n",
    "            s=list(index.keys())\n",
    "            root=trees[index[s[0]]]\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "        def test(i):\n",
    "            l=list()\n",
    "            def dfs(i):\n",
    "                if i==None:\n",
    "                    return\n",
    "                dfs(i.left)\n",
    "                l.append(i.val)\n",
    "                dfs(i.right)\n",
    "            dfs(i)\n",
    "            p=0\n",
    "            for i in l:\n",
    "                if i>p:\n",
    "                    p=i\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        if test(root):\n",
    "            return root\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMerge(self, trees):\n",
    "        root=dict()\n",
    "        index=dict()\n",
    "        for x,target in enumerate(trees):\n",
    "            root[target.val]=target\n",
    "            index[target.val]=x\n",
    "        saf=list()\n",
    "        def findleef(i):\n",
    "            if i.left==None and i.right==None:\n",
    "                return i.val\n",
    "            else:\n",
    "                if i.left!=None:\n",
    "                    son=findleef(i.left)\n",
    "                    if son!=0:\n",
    "                        ans.append((son,i,0))\n",
    "                if i.right!=None:\n",
    "                    son=findleef(i.right)\n",
    "                    if son!=0:\n",
    "                        ans.append((son,i,1))\n",
    "                return 0\n",
    "            \n",
    "        for i in trees:\n",
    "            ans=list()\n",
    "            findleef(i)\n",
    "            saf.append(ans)\n",
    "        R=0\n",
    "        while len(root)>1 and R<len(saf):\n",
    "            x=0\n",
    "            flag=0\n",
    "            if saf[R]==None:\n",
    "                R+=1\n",
    "                continue\n",
    "            while x<len(saf[R]): \n",
    "                i=saf[R][x]\n",
    "                if i[0] in root :\n",
    "                    if i[0]==trees[R].val:\n",
    "                        return None\n",
    "                    flag=1\n",
    "                    f=i[1]\n",
    "                    if i[2]==0:\n",
    "                        f.left=root[i[0]]\n",
    "                    else:\n",
    "                        f.right=root[i[0]]\n",
    "                    del root[i[0]]\n",
    "                    n=index[i[0]]\n",
    "                    del index[i[0]]\n",
    "                    \n",
    "                    if trees[n].left==None and trees[n].right==None:\n",
    "                        continue\n",
    "                    else:\n",
    "                        del saf[R][x]\n",
    "                        x-=1\n",
    "                        saf[R].extend(saf[n])\n",
    "                    saf[n]=None\n",
    "                x+=1\n",
    "            if flag==0:\n",
    "                R+=1\n",
    "        if len(index)==1:\n",
    "            s=list(index.keys())\n",
    "            root=trees[index[s[0]]]\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "        def test(i):\n",
    "            l=list()\n",
    "            def dfs(i):\n",
    "                if i==None:\n",
    "                    return\n",
    "                dfs(i.left)\n",
    "                l.append(i.val)\n",
    "                dfs(i.right)\n",
    "            dfs(i)\n",
    "            p=0\n",
    "            for i in l:\n",
    "                if i>p:\n",
    "                    p=i\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        if test(root):\n",
    "            return root\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMerge(self, trees):\n",
    "        root=dict()\n",
    "        index=dict()\n",
    "        for x,target in enumerate(trees):\n",
    "            root[target.val]=target\n",
    "            index[target.val]=x\n",
    "        saf=list()\n",
    "        def findleef(i):\n",
    "            if i.left==None and i.right==None:\n",
    "                return i.val\n",
    "            else:\n",
    "                if i.left!=None:\n",
    "                    son=findleef(i.left)\n",
    "                    if son!=0:\n",
    "                        ans.append((son,i,0))\n",
    "                if i.right!=None:\n",
    "                    son=findleef(i.right)\n",
    "                    if son!=0:\n",
    "                        ans.append((son,i,1))\n",
    "                return 0\n",
    "            \n",
    "        for i in trees:\n",
    "            ans=list()\n",
    "            findleef(i)\n",
    "            saf.append(ans)\n",
    "        R=0\n",
    "        while len(root)>1 and R<len(saf):\n",
    "            x=0\n",
    "            flag=0\n",
    "            if saf[R]==None:\n",
    "                R+=1\n",
    "                continue\n",
    "            while x<len(saf[R]): \n",
    "                i=saf[R][x]\n",
    "                if i[0] in root :\n",
    "                    if i[0]==trees[R].val:\n",
    "                        return None\n",
    "                    flag=1\n",
    "                    f=i[1]\n",
    "                    if i[2]==0:\n",
    "                        f.left=root[i[0]]\n",
    "                    else:\n",
    "                        f.right=root[i[0]]\n",
    "                    del root[i[0]]\n",
    "                    n=index[i[0]]\n",
    "                    del index[i[0]]\n",
    "                    \n",
    "                    if trees[n].left==None and trees[n].right==None:\n",
    "                        continue\n",
    "                    else:\n",
    "                        del saf[R][x]\n",
    "                        x-=1\n",
    "                        saf[R].extend(saf[n])\n",
    "                    saf[n]=None\n",
    "                x+=1\n",
    "            if flag==0:\n",
    "                R+=1\n",
    "        if len(index)==1:\n",
    "            s=list(index.keys())\n",
    "            root=trees[index[s[0]]]\n",
    "        else:\n",
    "            return None\n",
    "        \n",
    "        def test(i):\n",
    "            l=list()\n",
    "            def dfs(i):\n",
    "                if i==None:\n",
    "                    return\n",
    "                dfs(i.left)\n",
    "                l.append(i.val)\n",
    "                dfs(i.right)\n",
    "            dfs(i)\n",
    "            p=0\n",
    "            for i in l:\n",
    "                if i>p:\n",
    "                    p=i\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        if test(root):\n",
    "            return root\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        seen = set(t.val for t in trees)\n",
    "        s = set()\n",
    "        dic = defaultdict(list)\n",
    "        for t in trees:\n",
    "            dic[t.val] = [None, None]\n",
    "            s.add(t.val)\n",
    "            if t.left:\n",
    "                if t.left.val in seen:\n",
    "                    seen.remove(t.left.val)\n",
    "                s.add(t.left.val)\n",
    "                dic[t.val][0] = t.left.val\n",
    "            if t.right:\n",
    "                if t.right.val in seen:\n",
    "                    seen.remove(t.right.val)\n",
    "                s.add(t.right.val)\n",
    "                dic[t.val][1] = t.right.val\n",
    "        \n",
    "        if len(seen) != 1:\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(list(seen)[0])\n",
    "        q = deque([(root, inf, -inf)])\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            node, l, r = q.popleft()\n",
    "            cnt += 1\n",
    "            if node.val >= l or node.val <= r:\n",
    "                return None\n",
    "            if dic[node.val]:\n",
    "                if dic[node.val][0]:\n",
    "                    node.left = TreeNode(dic[node.val][0])\n",
    "                    q.append((node.left, min(l, node.val), r))\n",
    "                if dic[node.val][1]:\n",
    "                    node.right = TreeNode(dic[node.val][1])\n",
    "                    q.append((node.right, l, max(node.val, r)))\n",
    "\n",
    "        return root if cnt == len(s) else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        seen = set()\n",
    "        dic = defaultdict(list)\n",
    "        for t in trees:\n",
    "            dic[t.val] = [None, None]\n",
    "            seen.add(t.val)\n",
    "            if t.left:\n",
    "                seen.add(t.left.val)\n",
    "                dic[t.val][0] = t.left.val\n",
    "            if t.right:\n",
    "                seen.add(t.right.val)\n",
    "                dic[t.val][1] = t.right.val\n",
    "\n",
    "        # 父节点数组\n",
    "        fa = list(range(max(seen) + 1))\n",
    "\n",
    "        def find(x):\n",
    "            if x != fa[x]:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            x, y = find(x), find(y)\n",
    "            if x != y:\n",
    "                fa[x] = y\n",
    "\n",
    "        for t in trees:\n",
    "            if t.left:\n",
    "                union(t.left.val, t.val)\n",
    "            if t.right:\n",
    "                union(t.right.val, t.val)\n",
    "        \n",
    "        if len(set(find(x) for x in seen)) != 1:\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(find(trees[0].val))\n",
    "        q = deque([(root, inf, -inf)])\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            node, l, r = q.popleft()\n",
    "            cnt += 1\n",
    "            if node.val >= l or node.val <= r:\n",
    "                return None\n",
    "            if dic[node.val]:\n",
    "                if dic[node.val][0]:\n",
    "                    node.left = TreeNode(dic[node.val][0])\n",
    "                    q.append((node.left, min(l, node.val), r))\n",
    "                if dic[node.val][1]:\n",
    "                    node.right = TreeNode(dic[node.val][1])\n",
    "                    q.append((node.right, l, max(node.val, r)))\n",
    "\n",
    "        if cnt != len(seen):\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 存储所有叶节点值的哈希集合\n",
    "        leaves = set()\n",
    "        # 存储 (根节点值, 树) 键值对的哈希映射\n",
    "        candidates = dict()\n",
    "        for tree in trees:\n",
    "            if tree.left:\n",
    "                leaves.add(tree.left.val)\n",
    "            if tree.right:\n",
    "                leaves.add(tree.right.val)\n",
    "            candidates[tree.val] = tree\n",
    "        \n",
    "        # 存储中序遍历上一个遍历到的值，便于检查严格单调性\n",
    "        prev = float(\"-inf\")\n",
    "        \n",
    "        # 中序遍历，返回值表示是否有严格单调性\n",
    "        def dfs(tree: Optional[TreeNode]) -> bool:\n",
    "            if not tree:\n",
    "                return True\n",
    "            \n",
    "            # 如果遍历到叶节点，并且存在可以合并的树，那么就进行合并\n",
    "            if not tree.left and not tree.right and tree.val in candidates:\n",
    "                tree.left = candidates[tree.val].left\n",
    "                tree.right = candidates[tree.val].right\n",
    "                # 合并完成后，将树丛哈希映射中移除，以便于在遍历结束后判断是否所有树都被遍历过\n",
    "                candidates.pop(tree.val)\n",
    "            \n",
    "            # 先遍历左子树\n",
    "            if not dfs(tree.left):\n",
    "                return False\n",
    "            # 再遍历当前节点\n",
    "            nonlocal prev\n",
    "            if tree.val <= prev:\n",
    "                return False\n",
    "            prev = tree.val\n",
    "            # 最后遍历右子树\n",
    "            return dfs(tree.right)\n",
    "        \n",
    "        for tree in trees:\n",
    "            # 寻找合并完成后的树的根节点\n",
    "            if tree.val not in leaves:\n",
    "                # 将其从哈希映射中移除\n",
    "                candidates.pop(tree.val)\n",
    "                # 从根节点开始进行遍历\n",
    "                # 如果中序遍历有严格单调性，并且所有树的根节点都被遍历到，说明可以构造二叉搜索树\n",
    "                return tree if dfs(tree) and not candidates else None\n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 存储所有叶节点值的哈希集合\n",
    "        leaves = set()\n",
    "        # 存储 (根节点值, 树) 键值对的哈希映射\n",
    "        candidates = dict()\n",
    "        for tree in trees:\n",
    "            if tree.left:\n",
    "                leaves.add(tree.left.val)\n",
    "            if tree.right:\n",
    "                leaves.add(tree.right.val)\n",
    "            candidates[tree.val] = tree\n",
    "        \n",
    "        # 存储中序遍历上一个遍历到的值，便于检查严格单调性\n",
    "        prev = float(\"-inf\")\n",
    "        \n",
    "        # 中序遍历，返回值表示是否有严格单调性\n",
    "        def dfs(tree: Optional[TreeNode]) -> bool:\n",
    "            if not tree:\n",
    "                return True\n",
    "            \n",
    "            # 如果遍历到叶节点，并且存在可以合并的树，那么就进行合并\n",
    "            if not tree.left and not tree.right and tree.val in candidates:\n",
    "                tree.left = candidates[tree.val].left\n",
    "                tree.right = candidates[tree.val].right\n",
    "                # 合并完成后，将树丛哈希映射中移除，以便于在遍历结束后判断是否所有树都被遍历过\n",
    "                candidates.pop(tree.val)\n",
    "            \n",
    "            # 先遍历左子树\n",
    "            if not dfs(tree.left):\n",
    "                return False\n",
    "            # 再遍历当前节点\n",
    "            nonlocal prev\n",
    "            if tree.val <= prev:\n",
    "                return False\n",
    "            prev = tree.val\n",
    "            # 最后遍历右子树\n",
    "            return dfs(tree.right)\n",
    "        \n",
    "        for tree in trees:\n",
    "            # 寻找合并完成后的树的根节点\n",
    "            if tree.val not in leaves:\n",
    "                # 将其从哈希映射中移除\n",
    "                candidates.pop(tree.val)\n",
    "                # 从根节点开始进行遍历\n",
    "                # 如果中序遍历有严格单调性，并且所有树的根节点都被遍历到，说明可以构造二叉搜索树\n",
    "                return tree if dfs(tree) and not candidates else None\n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 存储所有叶节点值的哈希集合\n",
    "        leaves = set()\n",
    "        # 存储 (根节点值, 树) 键值对的哈希映射\n",
    "        candidates = dict()\n",
    "        for tree in trees:\n",
    "            if tree.left:\n",
    "                leaves.add(tree.left.val)\n",
    "            if tree.right:\n",
    "                leaves.add(tree.right.val)\n",
    "            candidates[tree.val] = tree\n",
    "        \n",
    "        # 存储中序遍历上一个遍历到的值，便于检查严格单调性\n",
    "        prev = float(\"-inf\")\n",
    "        \n",
    "        # 中序遍历，返回值表示是否有严格单调性\n",
    "        def dfs(tree: Optional[TreeNode]) -> bool:\n",
    "            if not tree:\n",
    "                return True\n",
    "            \n",
    "            # 如果遍历到叶节点，并且存在可以合并的树，那么就进行合并\n",
    "            if not tree.left and not tree.right and tree.val in candidates:\n",
    "                tree.left = candidates[tree.val].left\n",
    "                tree.right = candidates[tree.val].right\n",
    "                # 合并完成后，将树丛哈希映射中移除，以便于在遍历结束后判断是否所有树都被遍历过\n",
    "                candidates.pop(tree.val)\n",
    "            \n",
    "            # 先遍历左子树\n",
    "            if not dfs(tree.left):\n",
    "                return False\n",
    "            # 再遍历当前节点\n",
    "            nonlocal prev\n",
    "            if tree.val <= prev:\n",
    "                return False\n",
    "            prev = tree.val\n",
    "            # 最后遍历右子树\n",
    "            return dfs(tree.right)\n",
    "        \n",
    "        for tree in trees:\n",
    "            # 寻找合并完成后的树的根节点\n",
    "            if tree.val not in leaves:\n",
    "                # 将其从哈希映射中移除\n",
    "                candidates.pop(tree.val)\n",
    "                # 从根节点开始进行遍历\n",
    "                # 如果中序遍历有严格单调性，并且所有树的根节点都被遍历到，说明可以构造二叉搜索树\n",
    "                return tree if dfs(tree) and not candidates else None\n",
    "        \n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        rcnt = Counter()\n",
    "        mp = {}\n",
    "        e = {}\n",
    "        ye = {}\n",
    "        ec = 0\n",
    "        for r in trees:\n",
    "            rcnt[r.val] += 1\n",
    "            if r.left:\n",
    "                if (r.left.val, r.val) in e:\n",
    "                    return None\n",
    "                if r.left.val in ye:\n",
    "                    return None\n",
    "                ye[r.left.val] = 1\n",
    "                e[(r.val,r.left.val)] = 1\n",
    "                rcnt[r.left.val] -= 1\n",
    "                ec += 1\n",
    "            if r.right:\n",
    "                if (r.right.val, r.val) in e:\n",
    "                    return None\n",
    "                if r.right.val in ye:\n",
    "                    return None\n",
    "                ye[r.right.val] = 1\n",
    "                e[(r.val,r.right.val)] = 1\n",
    "                rcnt[r.right.val] -= 1\n",
    "                ec += 1\n",
    "            mp[r.val] = r\n",
    "\n",
    "        # print(mp.keys(), rcnt)\n",
    "\n",
    "        h = None\n",
    "        for i in trees:\n",
    "            if rcnt[i.val] > 0:\n",
    "                if h:\n",
    "                    return None\n",
    "                h = i\n",
    "        if not h:\n",
    "            return None\n",
    "        self.valid = 1\n",
    "        def chk(h, l, r):\n",
    "            # print(h, l, r)\n",
    "            x,y = h.val, h.val\n",
    "            if h.left:\n",
    "                if h.left.val in mp:\n",
    "                    h.left = mp[h.left.val]\n",
    "                    a,b = chk(h.left, l, h.val)\n",
    "                    if b >= h.val:\n",
    "                        self.valid = 0\n",
    "                    x = min(x, a)\n",
    "                x = min(x, h.left.val)\n",
    "            if h.right:\n",
    "                if h.right.val in mp:\n",
    "                    h.right = mp[h.right.val]\n",
    "                    a,b = chk(h.right, h.val, r)\n",
    "                    if a <= h.val:\n",
    "                        self.valid = 0\n",
    "                    y = max(y, b)\n",
    "                y = max(y, h.right.val)\n",
    "            # print(h,l,r,x,y, self.valid)\n",
    "            return x,y\n",
    "\n",
    "        chk(h, -inf, inf)\n",
    "        def vs(h):\n",
    "            r = 0\n",
    "            if h.left:\n",
    "                r += 1 + vs(h.left)\n",
    "            if h.right:\n",
    "                r += 1 + vs(h.right)\n",
    "            return r\n",
    "\n",
    "\n",
    "        if self.valid and vs(h) == ec:\n",
    "            return h\n",
    "\n",
    "        \n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        n = len(trees)\n",
    "        if n == 1:\n",
    "            return trees[0]\n",
    "\n",
    "        l = [1] * n\n",
    "        vals = defaultdict(set)\n",
    "        for i,t in enumerate(trees):\n",
    "            for j,x in enumerate([t.left, t.right], start=1):\n",
    "                if x:\n",
    "                    l[i] += 1\n",
    "                    vals[x.val].add((i,j))\n",
    "                if l[i] > 1:\n",
    "                    vals[t.val].add((i,0))\n",
    "        # check single nodes\n",
    "        for i in range(n):\n",
    "            if l[i] == 1 and trees[i].val not in vals:\n",
    "                return\n",
    "        \n",
    "        # merge\n",
    "        isRoot = [v > 1 for v in l]\n",
    "        for v,z in vals.items():\n",
    "            if len(z) == 1:\n",
    "                continue\n",
    "            if len(z) >= 3:\n",
    "                return\n",
    "            z = sorted(z, key=lambda a: a[-1])\n",
    "            i, a = z[0]\n",
    "            j, b = z[1]\n",
    "            if not (0 == a < b):\n",
    "                return\n",
    "            if b == 1:\n",
    "                trees[j].left = trees[i]\n",
    "            else:\n",
    "                trees[j].right = trees[i]\n",
    "            isRoot[i] = False\n",
    "\n",
    "        if sum(isRoot) != 1:\n",
    "            return\n",
    "        root = trees[isRoot.index(True)]\n",
    "        \n",
    "        seen = set()\n",
    "        def isBST(x, l, r):\n",
    "            if not x:\n",
    "                return True\n",
    "            if not (l < x.val < r):\n",
    "                return False\n",
    "            if not isBST(x.left, l, x.val):\n",
    "                return False\n",
    "            if not isBST(x.right, x.val, r):\n",
    "                return False\n",
    "            seen.add(x.val)\n",
    "            return True\n",
    "        \n",
    "        if not isBST(root, -math.inf, math.inf):\n",
    "            return\n",
    "        if len(seen) != len(vals):\n",
    "            return\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:\n",
    "        n = len(trees)\n",
    "        if n == 1:\n",
    "            return trees[0]\n",
    "\n",
    "        l = [1] * n\n",
    "        vals = defaultdict(set)\n",
    "        for i,t in enumerate(trees):\n",
    "            for j,x in enumerate([t.left, t.right], start=1):\n",
    "                if x:\n",
    "                    l[i] += 1\n",
    "                    vals[x.val].add((i,j))\n",
    "                if l[i] > 1:\n",
    "                    vals[t.val].add((i,0))\n",
    "        # check single nodes\n",
    "        for i in range(n):\n",
    "            if l[i] == 1 and trees[i].val not in vals:\n",
    "                return\n",
    "        \n",
    "        # merge\n",
    "        isRoot = [v > 1 for v in l]\n",
    "        for v,z in vals.items():\n",
    "            print(v, [x for x in z])\n",
    "            if len(z) == 1:\n",
    "                continue\n",
    "            if len(z) >= 3:\n",
    "                return\n",
    "            z = sorted(z, key=lambda a: a[-1])\n",
    "            i, a = z[0]\n",
    "            j, b = z[1]\n",
    "            if not (0 == a < b):\n",
    "                return\n",
    "            if b == 1:\n",
    "                trees[j].left = trees[i]\n",
    "            else:\n",
    "                trees[j].right = trees[i]\n",
    "            isRoot[i] = False\n",
    "\n",
    "        if sum(isRoot) != 1:\n",
    "            return\n",
    "        root = trees[isRoot.index(True)]\n",
    "        \n",
    "        seen = set()\n",
    "        def isBST(x, l, r):\n",
    "            if not x:\n",
    "                return True\n",
    "            if not (l < x.val < r):\n",
    "                return False\n",
    "            if not isBST(x.left, l, x.val):\n",
    "                return False\n",
    "            if not isBST(x.right, x.val, r):\n",
    "                return False\n",
    "            seen.add(x.val)\n",
    "            return True\n",
    "        # prev = -math.inf\n",
    "        # def isBST(x):\n",
    "        #     nonlocal prev\n",
    "        #     if x.left and isBST(x.left) == False:\n",
    "        #         return False\n",
    "        #     if prev >= x.val:\n",
    "        #         return False\n",
    "        #     prev = x.val\n",
    "        #     if x.right and isBST(x.right) == False:\n",
    "        #         return False\n",
    "        #     return True\n",
    "        \n",
    "        if not isBST(root, -math.inf, math.inf):\n",
    "            return\n",
    "        if len(seen) != len(vals):\n",
    "            return\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
